home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BIT_SET.H < prev    next >
C/C++ Source or Header  |  1992-09-25  |  15KB  |  381 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MBN 06/07/89 -- Initial design
  14. // Updated: LGO 08/09/89 -- Inherit from Generic
  15. // Updated: MBN 09/31/89 -- Added conditional exception handling
  16. // Updated: MBN 10/07/89 -- Changed operator[-~^&|] to allocate on stack
  17. //                          Bit_Set::find(int) returns state of indicated bit
  18. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and added
  19. //                          the current_position() method for Iterator<Type>
  20. // Updated: MBN 10/13/89 -- Changed from bit field to preprocessor bit macros
  21. // Updated: LGO 11/09/89 -- Major changes to every method
  22. // Updated: MBN 12/22/89 -- Sprinkled "const" qualifier all over the place!
  23. // Updated: DLS 03/26/91 -- New lite version
  24. // Updated: JAM 08/12/92 -- removed DOS specifics, stdized #includes
  25. // Updated: JAM 08/12/92 -- removed 'inline' from friend declarations
  26. // Updated: JAM 08/18/92 -- made *_state typedef a nested typedef "IterState"
  27. //                          as per new Iterator convention
  28. // Updated: JAM 09/26/92 -- changed #define ENVELOPE_* to #undef after
  29. //                          #include <Envelope.h> -- probably just typo
  30. //
  31. // The Bit Set class is publicy  derived from the  Generic class and implements
  32. // efficient bit  sets. These bits are stored  in an arbitrary length vector of
  33. // bytes  (unsigned char)  large  enough to represent   the specified number of
  34. // elements.  A  Bit Set is  indexed  by integer values.  Zero   represents the
  35. // first bit, one the second,  two third, and so  on with  each  integer  value
  36. // actually  indicating the  zero-relative  bit  position  in the  bit  vector.
  37. // Elements can be integers, enum values, constant symbols from the enumeration
  38. // package, or any   other type of   object or expression  that results  in  an
  39. // integral value.  All  operations that  involve bit shifting are performed in
  40. // byte  increments to affect the  most efficient operation on  common hardware
  41. // architectures.
  42. //
  43. // The Bit Set class is dynamic  in nature.  The  largest element integer value
  44. // determines the most most significant bit in the bit vector.  If a particular
  45. // value results in a bit index that is outside of the storage allocated, a new
  46. // vector of large  enough size  is created and the  appropriate bits set.  The
  47. // storage used  by the smaller vector is  returned  to  the heap.  The private
  48. // data section of  a Bit Set  has a slot that  points  to  the physical memory
  49. // allocated as unsigned  char,a  slot that maintains  the  count of  allocated
  50. // bytes, and a slot that maintains the current position.
  51. //
  52. // Three different constructors are provided.   The  first constructor takes no
  53. // arguments and creates a  Bit Set  that can accept BITSPERBYTE  elements (one
  54. // byte).  The second constructor accepts an integer argument and creates a Bit
  55. // Set that can accomodate at  least the specified  number of items.   Finally,
  56. // the third constructor takes  a single argument consisting  of a reference to
  57. // another Bit Set and duplicates its size and contents.
  58. //
  59. // Methods are provided to put, test, and remove an element from a set, perform
  60. // the intersection, union, difference, and exclusive-or of two sets, calculate
  61. // the complement of  a single set,  check equality and inequality of   two set
  62. // objects, and determine if one set is a subset of  another.  In addition, the
  63. // notion of a  current position within  a set is  maintained  and reset, next,
  64. // previous, find, and  get  value functions for setting and  using the current
  65. // position are provided.
  66. //
  67. // Also for use with the current position are the next union, next intersetion,
  68. // next difference, and  next exclusive-or operations.   These  allow a user to
  69. // access the first/next  individual  element that results   from  some logical
  70. // operation. These  functions are  particularly efficient for  looping through
  71. // the elements of a Bit Set, since no temporary Bit Set structure  is created.
  72. // Finally, methods to get the count of the  number of  items in  a set, output
  73. // the set to a stream, clear all elements from  a set, and determine  if a set
  74. // is empty are also available.
  75. //
  76. // Use envelope to avoid deep copy on return by value, and do set operations
  77. // in place.
  78.  
  79. #ifndef BIT_SETH                // If no Set class,
  80. #define BIT_SETH                // define it
  81.  
  82. #include <iostream.h>
  83.  
  84. #ifndef MISCELANEOUSH                // If no misc.h file
  85. #include <misc.h>            // Include useful defintions
  86. #endif    
  87.  
  88. #define BIT_SET_BLK_SZ 4
  89.  
  90. #define BS_BITSPERBYTE 8            // Number of bits in a byte
  91. #define BS_BYTE_OFFSET(n) ((int) (n & 0x07))    // These assume 8 bits per byte
  92. #define BS_BYTE_NUMBER(n) ((int) (n >> 3))
  93.  
  94. class CoolBit_SetE;                // Forward dec. of envelope
  95.  
  96. class CoolBit_Set {
  97. public:
  98.   typedef long IterState;            // Current position state
  99.  
  100.   CoolBit_Set ();                // bit set of zero byte size
  101.   CoolBit_Set (int);                // Bit set for at least size
  102.   CoolBit_Set (const CoolBit_Set&);        // Copy constructor
  103.   ~CoolBit_Set();                // Destructor
  104.  
  105.   CoolBit_Set& operator= (const CoolBit_Set&);    // Assignment operator
  106.   inline CoolBit_Set& operator= (CoolBit_SetE&);// Envelope back to Bit_Set
  107.  
  108.   inline void reset ();                // Invalidate current position
  109.   inline int value ();                // Value at current position
  110.   Boolean next ();                // Advance current position
  111.   Boolean prev ();                // Backup current position 
  112.   Boolean find (int);                // Return state of bit
  113.   inline IterState& current_position (); // Return current position
  114.   
  115.   Boolean put (int);                // Put element to set
  116.   Boolean put (int, int);            // Put range of elements to set
  117.   
  118.   Boolean remove ();                // Remove item current position
  119.   Boolean remove (int);                // Remove element from set
  120.   Boolean remove (int, int);            // Remove range from set
  121.  
  122.   inline Boolean is_empty () const;        // Return empty status
  123.   Boolean search (const CoolBit_Set&) const;    // Subset operator
  124.  
  125.   CoolBit_SetE operator- ();            // Complement of set
  126.   CoolBit_Set& operator|= (const CoolBit_Set&);    // Union of two sets
  127.   CoolBit_Set& operator-= (const CoolBit_Set&);    // Difference of two sets
  128.   CoolBit_Set& operator^= (const CoolBit_Set&);    // Exclusive-or of two sets
  129.   CoolBit_Set& operator&= (const CoolBit_Set&);    // Intersection of two sets
  130.  
  131.   inline CoolBit_SetE operator~ ();            // Complement of a set
  132.  
  133. // avoid deep copy and mutate in place with envelope
  134. //   inline friend CoolBit_SetE operator| (const CoolBit_Set&, const CoolBit_Set&);
  135. //   inline friend CoolBit_SetE operator- (const CoolBit_Set&, const CoolBit_Set&);
  136. //   inline friend CoolBit_SetE operator^ (const CoolBit_Set&, const CoolBit_Set&);
  137. //   inline friend CoolBit_SetE operator& (const CoolBit_Set&, const CoolBit_Set&);
  138.  
  139.   inline void set_union (const CoolBit_Set&);    // Union of two sets       
  140.   inline void set_difference (const CoolBit_Set&); // Difference of two sets  
  141.   inline void set_xor (const CoolBit_Set&);       // Exclusive-or of two sets
  142.   inline void set_intersection (const CoolBit_Set&); // Intersection of two sets
  143.  
  144.   Boolean next_union (const CoolBit_Set&);        // Next union item
  145.   Boolean next_difference (const CoolBit_Set&);    // Next differenceitem
  146.   Boolean next_xor (const CoolBit_Set&);        // Next exclusive-or 
  147.   Boolean next_intersection (const CoolBit_Set&);    // Next intersextion item
  148.  
  149.   int length () const;                // Return number of elements
  150.   void clear ();                // Empty the set
  151.   void resize (int);                // Resize for at least count
  152.   inline int capacity () const;            // Return maximum capacity
  153.   void set_growth_ratio (float);        // Set growth percentage
  154.   void set_alloc_size (int);            // Set alloc size
  155.  
  156.   inline Boolean operator[] (int) const;    // Return bit present status
  157.  
  158.   friend ostream& operator<< (ostream&, const CoolBit_Set&); // Overload output
  159.   friend ostream& operator<< (ostream&, const CoolBit_Set*);
  160.  
  161.   friend Boolean operator== (const CoolBit_Set&, const CoolBit_Set&);// Set equality test
  162.   friend Boolean operator!= (const CoolBit_Set&, const CoolBit_Set&); // Set inequality test
  163.  
  164. private:
  165.   int size;                    // Number of BYTES allocated
  166.   int number_elements;                // Index of last BYTE used
  167.   static int alloc_size_s;            // Allocation size for growth
  168.   float growth_ratio;                // If non-zero, growth ratio 
  169.   unsigned char* data;                // Allocated bit-vector
  170.   long curpos;                    // Bit index
  171.  
  172.   void grow (int min_size);            // Make the bitset bigger
  173.   void value_error () const;            // Raise exception
  174.   void bracket_error (int) const;        // Raise exception
  175.   void find_error (int) const;            // Raise exception
  176.   void put_error (int, int) const;        // Raise exception
  177.   void remove_error () const;            // Raise exception
  178.   void rem_start_end_error (int, int) const;    // Raise exception
  179. };
  180.  
  181. // Avoid deep copy, and do set operations in place with envelope
  182.  
  183. #define ENVELOPE_VERTICAL            // |= can be done in place
  184. #define ENVELOPE_AMPERSAND            // &= can be done in place
  185. #define ENVELOPE_MINUS                // -= can be done in place
  186. #define ENVELOPE_CARET                // ^= can be done in place
  187.  
  188. #define CoolLetter CoolBit_Set
  189. #define CoolEnvelope CoolBit_SetE
  190.  
  191. #include <cool/Envelope.h>            // Include envelope macros
  192.  
  193. #undef ENVELOPE_VERTICAL    
  194. #undef ENVELOPE_AMPERSAND    
  195. #undef ENVELOPE_MINUS        
  196. #undef ENVELOPE_CARET        
  197.  
  198. #undef CoolLetter
  199. #undef CoolEnvelope
  200.  
  201.  
  202. // operator=  -- Assignment from an envelope back to real set
  203. // Input:     envelope reference
  204. // Output:    Bit_Set reference with contents in envelope being swapped over
  205.  
  206. inline CoolBit_Set& CoolBit_Set::operator= (CoolBit_SetE& env){
  207.   env.shallow_swap((CoolBit_SetE*)this, &env);    // same physical layout
  208.   return *this;
  209. }
  210.  
  211.  
  212. // reset -- Reset the current position index
  213. // Input:   None
  214. // Output:  None
  215.  
  216. void CoolBit_Set::reset () {
  217.   this->curpos = INVALID;            // Invalidate current position
  218. }
  219.  
  220.  
  221. // value -- Return "position" of element at current position
  222. // Input:   None
  223. // Output:  Position of element in Set
  224.  
  225. inline int CoolBit_Set::value () {
  226. #if ERROR_CHECKING
  227.   if (this->curpos == INVALID)            // If INVALID current position
  228.     this->value_error ();            // Raise exception
  229. #endif
  230.   return (int) this->curpos;
  231. }
  232.  
  233.  
  234. // current_position () -- Return current position state
  235. // Input:                 None
  236. // Output:                Reference to current position state
  237.  
  238. inline CoolBit_Set::IterState& CoolBit_Set::current_position () {
  239.   return this->curpos;
  240. }
  241.  
  242.  
  243. // is_empty -- Return value indicating whether set contains any elements
  244. // Input:      None
  245. // Output:     TRUE/FALSE
  246.  
  247. inline Boolean CoolBit_Set::is_empty () const {
  248.   return ((this->length() == 0) ? TRUE : FALSE);
  249. }
  250.  
  251.  
  252. // operator~ -- Return complement of a set
  253. // Input:       None
  254. // Output:      Bit Set object containing complement of this set
  255.  
  256. inline CoolBit_SetE CoolBit_Set::operator~ () {
  257.   return (this->operator- ());
  258. }
  259.  
  260.  
  261. // // operator| -- Return the union of two sets, that is all elements in each set
  262. // // Input:       Reference to a bit set
  263. // // Output:      New Bit Set object containing union of two sets
  264. // 
  265. // inline CoolBit_Set CoolBit_Set::operator| (const CoolBit_Set& b) {
  266. //   CoolBit_Set result(*this);
  267. //   return result.operator|=(b);
  268. // }
  269. // 
  270. // 
  271. // // operator- -- Return the difference of two sets, that is all elements in the
  272. // //              the first set that are not in the second
  273. // // Input:       Reference to bit set
  274. // // Output:      New Bit Set object containing union of two sets
  275. // 
  276. // inline CoolBit_Set CoolBit_Set::operator- (const CoolBit_Set& b) {
  277. //   CoolBit_Set result(*this);
  278. //   return result.operator-=(b);
  279. // }
  280. // 
  281. // 
  282. // // operator^ -- Return the exclusive-OR of two sets, that is all elements in
  283. // //              the first set that are not in the second and all elements in
  284. // //              the second set that are not in the first
  285. // // Input:       Reference to bit set
  286. // // Output:      New Bit Set object containing XOR of two sets
  287. // 
  288. // inline CoolBit_Set CoolBit_Set::operator^ (const CoolBit_Set& b) {
  289. //   CoolBit_Set result(*this);
  290. //   return result.operator^=(b);
  291. // }
  292. // 
  293. // 
  294. // // operator& -- Return the intersection of two sets, that is all elements that
  295. // //              are in both sets
  296. // // Input:       Reference to Bit Set object
  297. // // Output:      New Bit Set object containing intersection of two sets
  298. // 
  299. // inline CoolBit_Set CoolBit_Set::operator& (const CoolBit_Set& b) {
  300. //   CoolBit_Set result(*this);
  301. //   return result.operator&=(b);
  302. // }
  303.  
  304.  
  305. // set_union -- Determine the union of two sets
  306. // Input:       Reference to a Bit Set object
  307. // Output:      None
  308.  
  309. inline void CoolBit_Set::set_union (const CoolBit_Set& b) {
  310.   this->operator|= (b);
  311. }
  312.  
  313.  
  314. // set_difference -- Determine the difference of two sets
  315. // Input:            Reference to a Bit Set object
  316. // Output:           None
  317.  
  318. inline void CoolBit_Set::set_difference (const CoolBit_Set& b) {
  319.   this->operator-= (b);
  320. }
  321.  
  322.  
  323. // set_xor -- Determine the exclusive-OR of two sets
  324. // Input:     Reference to a Bit Set object
  325. // Output:    None
  326.  
  327. inline void CoolBit_Set::set_xor (const CoolBit_Set& b) {
  328.   this->operator^= (b);
  329. }
  330.  
  331.  
  332. // set_intersection -- Determine the intersection of two sets
  333. // Input:              Reference to a Bit Set object
  334. // Output:             None
  335.  
  336. inline void CoolBit_Set::set_intersection (const CoolBit_Set& b) {
  337.   this->operator&= (b);
  338. }
  339.  
  340.   
  341. // operator!= -- Return logical result of not equal comparison test
  342. // Input:        Reference to another Bit Set object
  343. // Output:       Boolean TRUE/FALSE
  344.  
  345. inline Boolean operator!= (const CoolBit_Set& b1, const CoolBit_Set& b2){
  346.   return (!(b1 == b2));
  347. }
  348.  
  349.  
  350. // capacity -- Return maximum number of elements object can hold
  351. // Input:      None
  352. // Output:     Integer value of maximum number of elements
  353.  
  354. inline int CoolBit_Set::capacity () const {
  355.   return (this->size * BS_BITSPERBYTE);        // Maximum number of elements
  356. }
  357.  
  358.  
  359. // operator[] -- Return value of specified element 
  360. // Input:        Element to return value (really, it's just an integer value
  361. // Output:       None
  362.  
  363. inline Boolean CoolBit_Set::operator[] (int n) const {
  364. #if ERROR_CHECKING
  365.   if (n >= this->size * BS_BITSPERBYTE)        // If bit out of range
  366.     this->bracket_error (n);            // Raise exception
  367. #endif
  368.   return((this->data[BS_BYTE_NUMBER(n)]>>(BS_BYTE_OFFSET(n))) & 0x01);
  369. }
  370.  
  371.  
  372. // operator<< -- Overload the output operator for Bit Set objects
  373. // Input:        Reference to stream, pointer to Bit Set object
  374. // Output:       Reference to stream
  375.  
  376. inline ostream& operator<< (ostream& os, const CoolBit_Set* b) {
  377.   return operator<< (os, *b);
  378. }
  379.  
  380. #endif                        // End #ifdef of CoolBit_SetH
  381.